CS 420 Assignment 3 Winter 2004
1)
Given the following string, fill in the table:
OOOOHHH!!!AAAAAAHHH!WOOOOO!!!!
|
Letter |
ASCII |
Frequency |
Probability |
Information |
|
A |
0x41 |
|
|
|
|
H |
0x48 |
|
|
|
|
O |
0x4F |
|
|
|
|
W |
0x57 |
|
|
|
|
! |
0x21 |
|
|
|
2)
What is the first order entropy of the string in (1)?
3)
Use the ASCII codes to run-length encode the string in (1) as
would PCX.
4)
Encode the string in (1) in 8 bit RLE BMP format. Include an end-of-scan-line marker.
5)
a) Construct a Huffman code for the following letters.
b) What is the average code length in bits?
|
Probability |
Huffman code |
Bits in Huffman code |
|
|
E |
6/16 |
|
|
|
T |
5/16 |
|
|
|
A |
2/16 |
|
|
|
S |
1/16 |
|
|
|
D |
1/16 |
|
|
|
I |
1/16 |
|
|
6)
A BMP file uses uncompressed 4-bit pixels with the palette
below. The palette is given in the same
order as in the BMP file. For the
following hexadecimal string of pixels, give an ordered sequence of words
identifying the colors. For example,
your answer might take the form (yellow, yellow, yellow, blue, yellow, medium
gray, white).
CC01F2FFAF
|
Byte 1 |
Byte 2 |
Byte 3 |
Byte 4 |
Index |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
80 |
0 |
1 |
|
0 |
0 |
ff |
0 |
2 |
|
0 |
80 |
0 |
0 |
3 |
|
0 |
80 |
80 |
0 |
4 |
|
0 |
ff |
0 |
0 |
5 |
|
0 |
ff |
ff |
0 |
6 |
|
80 |
0 |
0 |
0 |
7 |
|
80 |
0 |
80 |
0 |
8 |
|
80 |
80 |
0 |
0 |
9 |
|
80 |
80 |
80 |
0 |
A |
|
c0 |
c0 |
c0 |
0 |
B |
|
ff |
0 |
0 |
0 |
C |
|
ff |
0 |
ff |
0 |
D |
|
ff |
ff |
0 |
0 |
E |
|
ff |
ff |
ff |
0 |
F |
